/*************************************************************************
	> File Name: thread_binary_tree.cpp
	> Author: 
	> Mail: 
	> Created Time: Sat 27 Jul 2024 10:16:52 AM CST
 ************************************************************************/

#include<iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;


typedef struct Node {
	int key;
	int ltag, rtag; // 1: thread, 0: edge
	struct Node *left, *right;
} Node;

Node *pre_node = nullptr;
Node *inorder_root = nullptr;

Node *getNewNode(int key) {
	Node *p = (Node *)malloc(sizeof(Node));
	p->key = key;
	p->left = p->right = nullptr;
	p->ltag = p->rtag = 0;
	return p;
}

Node *insert(Node *root, int key) {
	if(root == nullptr) return getNewNode(key);
	if(rand() % 2) root->left = insert(root->left, key);
	else root->right = insert(root->right, key);
	return root;
}

void pre_order(Node *root) {
	if(root == nullptr) return ;
	printf("%d ", root->key);
	if(root->ltag == 0) pre_order(root->left);
	if(root->rtag == 0) pre_order(root->right);
	return ;
}

void in_order(Node *root) {
	if(root == nullptr) return ;
	if(root->ltag == 0) in_order(root->left);
	printf("%d ", root->key);
	if(root->rtag == 0) in_order(root->right);
	return ;
}

void _build_inorder_thread(Node *root) {
	if(root == nullptr) return ;
	if(root->ltag == 0) _build_inorder_thread(root->left);
	if(root->left == nullptr) {
		root->left = pre_node;
		root->ltag = 1;
	}
	if(pre_node && pre_node->right == nullptr) {
		pre_node->right = root;
		pre_node->rtag = 1;
	}
	pre_node = root;
	printf("%d ", root->key);
	if(root->rtag == 0) _build_inorder_thread(root->right);
	return ;
}
void build_inorder_thread(Node *root) {
	_build_inorder_thread(root);
	pre_node->right = nullptr;
	pre_node->rtag = 1;
	return ;
}

void post_order(Node *root) {
	if(root == nullptr) return ;
	if(root->ltag == 0) post_order(root->left);
	if(root->rtag == 0) post_order(root->right);
	printf("%d ", root->key);
	return ;
}


Node *getNext(Node *root) {
	if(root->rtag == 1) return root->right;
	root = root->right;
	while(root->ltag == 0) root = root->left;
	return root;
}

Node *mostLeft(Node *root) {
	Node *tmp = root;
	while(tmp && tmp->ltag == 0) tmp = tmp->left;
	return tmp;
}
void clear(Node *root) {
	if(root == nullptr) return ;
	if(root->ltag == 0) clear(root->left);
	if(root->rtag ==0) clear(root->right);
	free(root);
	return ;
}
#define MAX_NODE 10
int main() {
	srand(time(0));
	Node *root = nullptr;
	for(int i = 0; i < MAX_NODE; i++) {
		root = insert(root, rand() % 100);
	}
	printf("pre_order\n");
	pre_order(root); // 前序遍历
	printf("\n\n");
	printf("in_order\n");
	in_order(root); // 中序遍历
	printf("\n\n");
	printf("post_order\n");
	post_order(root); // 后序遍历
	printf("\n\n");
	printf("build inorder thread : \n"); // build in
	build_inorder_thread(root);
	printf("\n\n");
	// 中序线索化后非递归遍历
	Node *node = mostLeft(root);
	while(node) {
		printf("%d-> ", node->key);
		node = getNext(node);
	}
	printf("\n\n");


	clear(root);
	return 0;
}
